package demo;
import java.util.Arrays;
public class Sort {
    //插入排序
    public static void insertSort(int[]array){
        int size=array.length;
        //令j一直是i的第前一个位置
        for(int i=1;i<size;i++){
            //保存array[i] 为temp
            int temp=array[i];
            int j=i-1;
            //array[j]>temp时右移 后j--
            for( j=i-1;j>=0&&array[j]>temp;j--){
                array[j+1]=array[j];
            }
            //找到合适位置 temp放到j+1位置
            array[j+1]=temp;
        }
    }
    //希尔排序：先对数组进行分组，采用每组分为两个2个元素得出组数，组数即使是增量
    public static void shellSort(int[]array){
        //求数组长度
        int gap=array.length;
        //循环求增量
        while(true){
            //当增量为1已经经有序，退出循环
            if(gap==1){
                return ;
            }
            //每次求增量
            gap=gap/2;
            //求得增量后排序，传入数组和增量排序
            shellSortWithGap(array, gap);
        }
    }
    //希尔排序
    public static void shellSortWithGap(int[]array,int gap){
        for(int i=gap;i<array.length;i++){
            int temp=array[i];
            int j=i-gap;
            for(j=i-gap;j>=0&&array[j]>temp;j=j-gap){
                array[j+gap]=array[j];
            }
            array[j+gap]=temp;
        }
    }

    public static void main(String[] args) {
        int[]arr={1,77,41,55,2,4,4,66};
        shellSort(arr);
        System.out.println("希尔排序："+Arrays.toString(arr));
        int[]arr2={1,0,99,88,78,199,5,9,42};
        insertSort(arr2);
        System.out.println("插入排序："+Arrays.toString(arr2));
    }
   
}
